/*  
 * i-OSGi - Tunable Bundle Isolation for OSGi
 * Copyright (C) 2011  Sven Schulz
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package org.iosgi.impl.engine;

import java.util.concurrent.TimeUnit;

import org.iosgi.util.lang.Longs;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import algorithms.graphColorer.Colorer;
import algorithms.graphColorer.heuristics.GreedyColorer;
import algorithms.graphColorer.heuristics.GreedyStrategy;
import algorithms.graphColorer.reoptimizer.IteratedGreedyColorer;
import dataStructures.graph.ExtendedUndirectedGraph;
import dataStructures.graph.GraphColoring;

/**
 * @author Sven Schulz
 */
public class RoundBasedIteratedGreedyColorer<V extends Comparable<? super V>, E>
		implements ReportingColorer<V, E> {

	private static final Logger LOGGER = LoggerFactory
			.getLogger(RoundBasedIteratedGreedyColorer.class);

	private final ExtendedUndirectedGraph<V, E> graph;
	private final int rounds;

	public RoundBasedIteratedGreedyColorer(
			final ExtendedUndirectedGraph<V, E> graph, int rounds) {
		this.graph = graph;
		this.rounds = rounds;
	}

	@Override
	public GraphColoring<V, E> getColoring() {
		return this.getColoring(null, Long.MAX_VALUE, TimeUnit.DAYS);
	}

	@Override
	public GraphColoring<V, E> getColoring(ReportListener<V, E> listener,
			long timeout, TimeUnit unit) {

		long baseref = System.nanoTime();

		long deadline = Longs.saturatedAdd(System.currentTimeMillis(),
				TimeUnit.MILLISECONDS.convert(timeout, unit));

		/* Create initial coloring. */
		Colorer<V, E> colorer = new GreedyColorer<V, E>(graph,
				new GreedyStrategy<V, E>());
		GraphColoring<V, E> coloring = colorer.getColoring();
		LOGGER.debug("computed initial coloring with {} colors in {} ns",
				coloring.getNumberOfColors(), System.nanoTime() - baseref);
		if (listener != null) {
			listener.handle(this, coloring);
		}

		/* Perform rounds with exponentially increasing iterations. */
		for (int r = 0; r < rounds; r++) {
			long stepref = System.nanoTime();
			int maxIterations = (int) Math.pow(2, r);
			colorer = new IteratedGreedyColorer<V, E>(graph, maxIterations,
					coloring);
			coloring = colorer.getColoring();
			if (Thread.currentThread().isInterrupted()
					|| System.currentTimeMillis() > deadline) {
				break;
			}
			long now = System.nanoTime();
			LOGGER.debug(
					"computed round {} coloring ({} maximum iterations) with {} colors in {}/{} ns",
					new Object[] { r + 1, maxIterations,
							coloring.getNumberOfColors(), now - stepref,
							now - baseref });
			if (listener != null) {
				listener.handle(this, coloring);
			}
		}
		return coloring;
	}

}